package com.LeeCode;

/**
 * 两个字符串的最小ASCII删除和
 */

public class Code712 {
    public static void main(String[] args) {
        String s1 = "delete", s2 = "delete";
        System.out.println(new Code712().minimumDeleteSum(s1, s2));
    }

    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }

        for (int i = 1; i <= n; i++) {
            dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int aux = s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : s1.charAt(i - 1) + s2.charAt(j - 1);
                dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + aux);
            }
        }
        return dp[m][n];
    }
}
